package algo.A04_快速排序和归并排序;

import util.ArrayUtil;


/**
 * 给定一个整数数组，如何快速地求出该数组中第k小的数。假如数组为{4，0，1，0，2，3}，那么第3小的元素是1。
 */
public class T02_找出第k小的数_非常重要 {
    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(10, 0, 100);
        ArrayUtil.print(arr);
        int result = solution(arr, 0, arr.length - 1, 2);
        System.out.println("result = " + result);
    }

    /**
     * 解题思路：快速排序，当基准所在下标就是要找的下标时，返回即可
     *
     * @param A 原数组
     * @param p 左侧边界
     * @param r 右侧边界
     * @param k 找第k小的元素，当K为长度的一半时，则找中位数
     * @return
     */
    private static int solution(int[] A, int p, int r, int k) {
        int q = partition2(A, p, r);//获取中间值(基准)下标，基准左边比基准小，基准右边比基准大，基准在第几个->基准是第k小
        int qk = q - p + 1;//获取基准是第几个元素(此处qk不是下标，是从1开始数的)
        //基准所在位置等于要找的位置时，说明当前位置就是要找的元素
        if (qk == k) {
            return A[q];
        } else if (qk > k) {
            //基准所在位置在要找的位置的右边时，说明答案在基准左边
            return solution(A, p, q - 1, k);
        } else {
            //基准所在位置在要找的位置的左边时，说明答案在基准右边
            //因为传递的是基准右边的数组，因此参数k也要减去基准的位置
            return solution(A, q + 1, r, k - qk);
        }
    }

    /**
     * 单向扫描
     *
     * @param A
     * @param p
     * @param r
     * @return
     */
    private static int partition1(int[] A, int p, int r) {
        int pivot = A[p];
        int sp = p + 1;
        int bigger = r;
        while (sp <= bigger) {
            if (A[sp] > pivot) {
                ArrayUtil.swap(A, sp, bigger);
                bigger--;
            } else {
                sp++;
            }
        }
        ArrayUtil.swap(A, p, bigger);
        return bigger;
    }

    /**
     * 双向扫描
     *
     * @param A
     * @param p
     * @param r
     * @return
     */
    private static int partition2(int[] A, int p, int r) {
        int pivot = A[p];
        int left = p + 1;
        int right = r;
        while (left <= right) {
            //找下一个左边大于基准的值
            while (left <= right && A[left] <= pivot) {
                left++;
            }
            //找下一个右边小于等于基准的值
            while (left <= right && A[right] > pivot) {
                right--;
            }
            if (left < right) {
                ArrayUtil.swap(A, left, right);
            }
        }
        ArrayUtil.swap(A, p, right);
        return right;
    }
}
